#include <iostream>
#include <vector>
#include <string>
using namespace std;

//vector<int> KMP(const string& s)
//{
//	int n = s.size();
//	vector<int> next(n + 1);
//	
//	next[0] = -1;
//	
//	for (int i = 1; i < n; i++)
//	{
//		int p = i - 1, k = next[p];
//		char ch1 = s[p],ch2;
//		if (k == -1) ch2 = s[0];
//		else ch2 = s[k];
//		while (ch1 != ch2)
//		{
//			if (p == 0)
//			{
//				k = -1;
//				break;
//			}
//			p = next[p];
//			k = next[p];
//			if (k == -1) ch2 = s[0];
//			else ch2 = s[k];
//		}
//		next[i] = k + 1;
//	}
//
//	return next;
//}

vector<int> KMP(const string& s)
{
	int n = s.size();
	vector<int> next(n + 1);
	vector<int> nextval(n + 1);
	next[0] = nextval[0] = - 1;

	for (int i = 1; i < n; i++)
	{
		int p = i - 1,k = next[p];
		char ch1 = s[p],ch2;
		if (k == -1) ch2 = s[0];
		else ch2 = s[k];
		if (ch1 != ch2 && k != -1)k = nextval[k];
		next[i] = k + 1;

		if (s[i] == s[next[i]]) nextval[i] = next[next[i]];
		else nextval[i] = next[i];
	}

	return next;
}



int main()
{
	KMP("abcababcabc");
	return 0;
}
